#pragma comment(linker, "/STACK.64000000")

#include <cstdio>

struct Node
{
	int key, index;
};

Node a[7], b[7];
int si = 0;

void swap(int &a_, int &b_)
{
	int t = a_; a_ = b_; b_ = t;
}

void ShiftUp_max(int i)
{
	if (i == 1) return;
	if (a[i].key > a[i / 2].key)
	{
		swap(a[i].key, a[i / 2].key);
		swap(a[i].index, a[i / 2].index);
		swap(b[a[i].index].index, b[a[i / 2].index].index);
		ShiftUp_max(i / 2);
	}
}

void ShiftDown_max(int i)
{
	if (2 * i > si) return;
	if (2 * i == si)
	{
		if (a[2 * i].key > a[i].key)
		{
			swap(a[i].key, a[i * 2].key);
			swap(a[i].index, a[i * 2].index);
			swap(b[a[i].index].index, b[a[i * 2].index].index);
			return;
		}
		return;
	}
	int t = -1;
	if (a[2 * i + 1].key >= a[2 * i].key)
		t = 2 * i + 1;
	if (a[2 * i].key > a[2 * i + 1].key)
		t = 2 * i;
	if (t != -1 && a[t].key > a[i].key) 
	{
		swap(a[i].key, a[t].key);
		swap(a[i].index, a[t].index);
		swap(b[a[i].index].index, b[a[t].index].index);
		ShiftDown_max(t);
	}
	return;
};

void ShiftUp_min(int i)
{
	if (i == 1) return;
	if (b[i].key < b[i / 2].key)
	{
		swap(b[i].key, b[i / 2].key);
		swap(b[i].index, b[i / 2].index);
		swap(a[b[i].index].index, a[b[i / 2].index].index);
		ShiftUp_min(i / 2);
	}
}

void ShiftDown_min(int i)
{
	if (2 * i > si) return;
	if (2 * i == si)
	{	
		if (b[2 * i].key < b[i].key)
		{
			swap(b[i].key, b[i * 2].key);
			swap(b[i].index, b[i * 2].index);
			swap(a[b[i].index].index, a[b[i * 2].index].index);
			return;
		}
		return;
	}
	int t = -1;
	if (b[2 * i + 1].key <= b[2 * i].key)
		t = 2 * i + 1;
	if (b[2 * i].key < b[2 * i + 1].key)
		t = 2 * i;
	if (t != -1 && b[t].key < b[i].key) 
	{
		swap(b[i].key, b[t].key);
		swap(b[i].index, b[t].index);
		swap(a[b[i].index].index, a[b[t].index].index);
		ShiftDown_min(t);
	}
	return;
};

int ExtractMax()
{
	int t = a[1].key;
	int ida1 = a[1].index;
	int idas = a[si].index;
	int idbs = b[si].index;
	b[idas].index = 1;
	a[idbs].index = ida1; 
	a[1].key = a[si].key;
	a[1].index = a[si].index;
	b[ida1].key = b[si].key;
	b[ida1].index = b[si].index;
	b[si].key = 0;
	b[si].index = 0;
	a[si].key = 0;
	a[si].index = 0;
	si--;
	ShiftDown_max(1);
	if (ida1 > si) return t;
	ShiftDown_min(ida1);
	ShiftUp_min(ida1);
	return t;
}

int ExtractMin()
{
	int t = b[1].key;
	int idb1 = b[1].index;
	int idbs = b[si].index;
	int idas = a[si].index;
	a[idbs].index = 1;
	b[idas].index = idb1; 
	b[1].key = b[si].key;
	b[1].index = b[si].index;
	a[idb1].key = a[si].key;
	a[idb1].index = a[si].index;
	a[si].key = 0;
	a[si].index = 0;
	b[si].key = 0;
	b[si].index = 0;
	si--;
	ShiftDown_min(1);
	if (idb1 > si) return t;
	ShiftDown_max(idb1);
	ShiftUp_max(idb1);
	return t;
}

void Insert(int x)
{
	si++;
	a[si].key = x;
	a[si].index = si;
	b[si].key = x;
	b[si].index = si;
	ShiftUp_max(si);
	ShiftUp_min(si);
}

int main ()
{
	freopen("minimax.in", "r", stdin);
	freopen("minimax.out", "w", stdout);
	int n;
	int x;
	scanf("%d\n", &n);
	for (int i = 0; i < n; i++)
	{
		char c;
		scanf("%c", &c);
		if (c == 'I')
		{
			scanf("nsert(%d)\n", &x);
			Insert(x);
		}
		if (c == 'E')
		{
			char d;
			scanf("xtractM%c%c\n", &c, &d);
			if (c == 'i')
				printf("%d\n", ExtractMin());
			if (c == 'a')
				printf("%d\n", ExtractMax());
		}
	}
}